// create by IAmFiveHigh on 2024/7/19

class LinkListNode<T>() {
    var e: T? = null
    var next: LinkListNode<T>? = null

    constructor(e: T? = null) : this() {
        this.e = e
    }
}

open class LinkList<T> {
    private var dummyNode: LinkListNode<T> = LinkListNode()
    private var size: Int = 0

    fun getSize(): Int {
        return this.size
    }

    fun isEmpty(): Boolean {
        return this.size == 0
    }

    fun insertElement(e: T, index: Int) {
        if (index < 0 || index > this.size) {
            return
        }

        var pre: LinkListNode<T>? = this.dummyNode
        for (i in 0 until index) {
            pre = pre?.next
        }
        val node = LinkListNode(e)
        node.next = pre?.next
        pre?.next = node
        this.size += 1
    }

    fun addFirst(e: T) {
        this.insertElement(e, 0)
    }

    fun addLast(e: T) {
        this.insertElement(e, this.size)
    }

    fun deleteElementByIndex(index: Int): T? {
        if (index < 0 || index >= this.size) {
            return null
        }

        var pre: LinkListNode<T>? = this.dummyNode
        for (i in 0 until index) {
            pre = pre?.next
        }
        val node = pre?.next
        pre?.next = node?.next
        node?.next = null
        this.size -= 1
        return node?.e
    }

    fun deleteFirst(): T? {
        return this.deleteElementByIndex(0)
    }

    fun deleteLast(): T? {
        return this.deleteElementByIndex(this.size - 1)
    }

    /// 返回链表内部的元素遍历
    fun traversalList(): List<T> {
        var pre: LinkListNode<T>? = this.dummyNode
        val resultList = mutableListOf<T>()
        for (i in 0 until this.size) {
            pre = pre?.next
            pre?.let { node ->
                node.e?.let {
                    resultList.add(it)
                }
            }
        }
        return resultList.toList()
    }
}